package com.learn.algorlthm;

/**
 * @classname:
 * @Description:链表中环的入口结点
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-07-24 17:38
 *
 * 题目描述：
 * 一个链表中包含环，请找出该链表的环的入口结点。
 * 要求不能使用额外的空间。
 */
public class Learn23 {

    /**
     * 解题思路：
     * <p>
     * 使用双指针，一个指针fast每次移动两个节点，一个指针slow每次移动一个节点。因为存在环，所以两个指针必定相遇在环
     * 中的某个节点上。假设相遇点在下图的z1位置，此时fast移动的节点数为x+2y+z,slow为x+y，由于fast速度比slow快一
     * 倍，因此x+2+z=2(x+y),得到x=z。
     * <p>
     * 在相遇占，slow要到环的入口点还需要移动z个节点，如果让fast重新开始移动，并且速度为每次移动一个节点，那么它到环
     * 入口点还需要移动x个节点。在上面已经推导出x=x,因此fast和slow将在环入口点相遇
     */
    private static ListNode listNode;

    public static ListNode entryNodeOfLoop(ListNode pHead) {
        ListNode fast = pHead, slow = pHead;

        do {
            fast = fast.next.next;
            slow = slow.next;
        }while (fast != slow);

        fast = pHead;

        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }



    static class ListNode {
        public String val;
        public ListNode next;
    }

    public static ListNode getListNode() {
        if (listNode == null) {
            listNode = new ListNode();
            ListNode a = listNode;
            ListNode startNode = null;

            for (int i = 1; i < 11; i++) {
                if (i <= 3)
                    a.val = "x"+i;
                else if (i <= 7)
                    a.val = "y"+(i-3);
                else if (i <= 10)
                    a.val = "z"+(i-7);

                a.next = new ListNode();
                if (i == 3)
                    startNode = a;
                if (i == 10)
                    a.next = startNode;
                a = a.next;
            }
        }

        return listNode;
    }
}
